<?php

/**
 * 单循环链表
 *
 * 循环链表和单链表相似，节点类型都是一样的。
 * 唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即:head.next = head，
 * 这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。
 * 换句话说，链表的尾节点指向头节点，形成了一个循环链表。
 */

class Node
{
    public $data;//节点数据
    public $next;//后继节点
    
    public function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}

class CircularLinkedList
{
    public $header;//头节点
    
    public function __construct($data)
    {
        $this->header = new Node($data);
        $this->header->next = $this->header;
        
        $this->show();
    
    }
    
    /**
     * 查找节点
     *
     * @param string $item 节点数据
     *
     * @return object
     */
    public function find($item)
    {
        $current = $this->header;
        while($current->data != $item)
        {
            $current = $current->next;
        }
        
        return $current;
    }
    
    /**
     * 查找节点的前一个节点
     *
     *@param string $item 节点数据
     *
     * @return object
     */
    public function findPreByCurrentNode($item)
    {
        $current = $this->header;
        while($current->next != null && $current->next->data != $item)
        {
            $current = $current->next;
        }
        
        return $current;
    }
    
    /**
     * 插入新节点
     *
     * @param string $item  节点数据
     * @param string $new   插入的节点数据
     *
     * @return boolean
     */
    public function insert($item,$new)
    {
        $current = $this->find($item);
        $new     = new Node($new);
        
        //链表中间
        if ($current->next != $this->header)
        {
            $new->next = $current->next;
            $current->next = $new;
        }
        else//链表尾端
        {
            $current->next = $new;
            $new->next = $this->header;
        }
        
        return true;
    }
    
    /**
     * 删除节点
     *
     * @param string $item 节点数据
     *
     * @return boolean
     */
    public function delete($item)
    {
        $current = $this->find($item);
        $pre = $this->findPreByCurrentNode($item);
        
        //链表中间
        if ($current->next != $this->header)
        {
            $pre->next = $current->next;
        }
        else//链表尾端
        {
            $pre->next = $this->header;
        }
    }
    
    /**
     * 显示
     */
    public function show()
    {
        $current = $this->header;
        while($current->next != $this->header)
        {
            echo $current->next->data."  ";
            $current = $current->next;
        }
    }
}

//插入
$circular_linked_list = new CircularLinkedList('header');
$circular_linked_list->insert('header','A');
$circular_linked_list->insert('A','B');
$circular_linked_list->insert('B','C');
$circular_linked_list->insert('C','D');
$circular_linked_list->show();


//删除
echo PHP_EOL;
$circular_linked_list->delete('C');
$circular_linked_list->show();
